import java.util.Arrays;

class Solution {
    public int findNumberOfLIS(int[] nums) {
        // 创建dp表、初始化、填表、返回值

        int n = nums.length;
        int[] len = new int[n]; // 记录最长递增子序列的长度
        int[] count = new int[n]; // 记录最长递增子序列的个数

        Arrays.fill(len, 1);
        Arrays.fill(count, 1);

        for (int i = 1; i < n; i++) { // 求整个dp数组
            for (int j = i-1; j >= 0; j--) { // 求单个dp数组的值
                if (nums[j] < nums[i]) { // 满足严格递增
                    if (len[j] + 1 > len[i]) {
                        // 更新最长长度以及计数器
                        len[i] = len[j] + 1;
                        count[i] = count[j];
                    } else if (len[j] + 1 == len[i]) {
                        // 更新计数器
                        count[i] += count[j];
                    }
                }
            }
        }

        int max = len[0], ret = 1;
        for (int i = 1; i < n; i++) {
            if (len[i] > max) {
                // 重置最大值以及计数器
                max = len[i];
                ret = count[i];
            } else if (len[i] == max) {
                // 更新计数器
                ret += count[i];
            }
        }

        return ret;
    }
}